public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
//        System.out.println(s.hammingWeight(-1));
//        int[] ret = s.countBits(5);
//        for(int x: ret) {
//            System.out.print(x + " ");
//        }
//        System.out.println(s.hammingDistance(3,1));
//        int[] nums = new int[]{4,1,2,1,4};
//        System.out.println(s.singleNumber(nums));
        int[] arr = new int[]{1,2,3,4,4,1};
        for(int e: s.singleNumber(arr)) {
            System.out.println(e);
        }
    }

    public static int hammingWeight(int n) {
        /**
         * 位1的个数
         * 有一个思路：
         *  1，值不为0，就将其最右边的1修改为0
         *  2，重复上述操作，直至目标值为0（即无1）
         * */
        // 1 预处理
        int count = 0;

        // 2 执行逻辑（每次消除1，直至为0）
        while(n != 0) {
            count ++;
            n &= (n-1);
        }

        // 3 返回值
        return count;
    }

    public int[] countBits(int n) {
        /**
         * 比特位计数*/
        // 1 预处理
        int[] ret = new int[n+1];
        for(int i = 0; i <= n; i++) {
            ret[i] = hammingWeight(i);
        }

        // 2 返回值
        return ret;
    }

    public int hammingDistance(int x, int y) {
        /**
         * 汉明距离
         *  思路：
         *  使用按位异或，因为相同为0，不同为1，我们只需要找到1的个数即可*/
        // 1 预处理
        int z = x ^ y;
        int count = 0;

        // 2 执行逻辑
        while(z != 0) {
            count ++;
            z &= (z-1);
        }

        // 3 返回值
        return count;
    }

    // 休息十分钟，到20：57 //休息完成，现在21：02

    public int singleNumber1(int[] nums) {
        /**
         * 只出现一次的数字*/
        int n = nums[0];
        for(int i = 1; i < nums.length; i++) {
            n ^= nums[i];
        }
        return n;
    }

    public int[] singleNumber2(int[] nums) {
        /**
         * 只出现过一次的数字Ⅲ
         *  思路：
         *      若是我们将所有元素按位异或在一起，那么最终的结果就是两个只出现一次的元素异或结果
         *      那么我们是否是要去通过最终结果反推元素呢？*/
        // 1 预处理
        int firstResult = nums[0];

        // 2 循环第一次，将数组中所有元素异或
        // 最终的结果就是只出现一次的两个元素异或（这两个元素必定不相等）
        for(int i = 1; i < nums.length; i++) {
            firstResult ^= nums[i];
        }

        // 3 因为两个元素都只出现一次，故必定不相等
        // 我们找到其异或后第一个1所在位置，随后将数组中的元素以这个位置值划分为两组
        int index = 0;
        for(int i = 0; i <= 32; i++) {
            if(((firstResult >> i) & 1) == 1) {
                index = i;
                break;
            }
        }

        // 4 分组异或，最终这两个单独的元素一定是分开的
        int x1 = 1;
        int x2 = 1;
        for(int e: nums) {
            if(((e >> index) & 1) == 1) {
                x1 ^= e;
            } else {
                x2 ^= e;
            }
        }
        x1 ^= 1;
        x2 ^= 1;

        // 5 返回值
        return new int[]{x1, x2};
    }

    public int[] singleNumber(int[] nums) {
        /**
         * 只出现过一次的数字Ⅲ
         *  思路：
         *      优化*/
        // 1 预处理
        int firstResult = nums[0];

        // 2 获得单独元素异或结果
        for(int i = 1; i < nums.length; i++) {
            firstResult ^= nums[i];
        }

        // 3 找到异或第一个1所在位置
        int lowBit = firstResult & (-firstResult);

        // 4 分组异或，最终这两个单独的元素一定是分开的
        int x1 = 1;
        int x2 = 1;
        for(int e: nums) {
            // -lowBit后，假设其二进制表示为0010，我们让其按位&一个元素
            // 由于lowBit二进制仅有一个1，若是枚举元素对应也为1则值不为0，否则为0，因为按位与有0为0
            if((e & lowBit) == 0) {
                x1 ^= e;
            } else {
                x2 ^= e;
            }
        }
        x1 ^= 1;
        x2 ^= 1;

        // 5 返回值
        return new int[]{x1, x2};
    }

    // 休息十分钟，至22：05 //休息完成，现在22：10
}
